package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.Stack;

/**
 * see 889 105 106
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC105_1 implements TreeProblem, StackProblem {

    public TreeNode buildTree(int[] preorder/*中左右*/, int[] inorder/*左中右*/) {
        int len = preorder.length;
        if (len == 0 || len != inorder.length) return null;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.push(root);
        TreeNode node = null;

        for (int i = 1, j = 0; i < len; i++) {
            TreeNode cur = new TreeNode(preorder[i]);
            while (!stack.isEmpty() &&
                    stack.peek().val == inorder[j]) {
                node = stack.pop();
                j++;
            }
            if (node != null) {
                node.right = cur;
                node = null;
            } else {
                stack.peek().left = cur;
            }
            stack.push(cur);
        }

        return root;
    }

    public void addChild(TreeNode a, TreeNode b) {
        if (a.left == null) {
            a.left = b;
        } else {
            a.right = b;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 6, 5, 8, 12, 14, 4, 7, 11, 9, 13, 10, 15};//preorder/*中左右*/
        int[] b = {6, 3, 2, 12, 14, 8, 5, 1, 11, 7, 13, 9, 4, 15, 10};//inorder/*左中右*/
        TreeNode xx = new LC105_1().buildTree(a, b);
        System.out.println(xx);
    }
}
